/**
 * @author ChaP
 * @date 2019/06/09
 * @describe:
 */
package CodingTest.AC20190609;

/**
 * dp[i][j]表示索引i到j的子串是否是回文
 dp[i][j] = true表示是回文，反之则为false

 dp[i][i]只有一个字符，必是回文
 关键点在于找到关系：dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
 长的子串dp[i][j]依赖于短的子串dp[i + 1][j - 1]，所以由短到长依次计算
 1、先计算一个字符，全为true
 2、再计算两个字符，如果两个字符一样则为true
 3、然后计算大于三个字符，直到整个字符串
 */
//动态规划
public class longestPalindrome {
    public String longestPalindrome(String s){
        int len = s.length();
        boolean[][] dp = new boolean[len][len]; //定义二维数组存储dp的结果值
        String result = s.substring(0,1);
        for(int i = 0;i<len;i++){
            dp[i][i]= true; //单个字符（起点终点索引相同）全部为true
        }
        for(int i = 0;i<len-1;i++){
            dp[i][i+1] = s.charAt(i) == s.charAt(i+1); //两个字符如果字符相同为true（注意数组不要越界）
            if(dp[i][i+1]){
                result = s.substring(i,i+1+1);
            }
        }
        // 依次循环三个字符、四个字符......
        for(int k = 3;k<=len;k++){
            for(int i = 0;(i+k)<=len;i++){
                //有起点索引 i，有子串长度 k 则可以得到终点索引 j （同样注意数组越界问题）
                int j = i+k-1;
                dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j);
                if(dp[i][j]&&(j-i+1)>result.length()){
                    // 比较回文子串长度与保存的result长度
                    result = s.substring(i,j+1);
                }

            }
        }
        return result;

    }
}
